
#include "rx_automaton.h"
#include "rx_mem.h"
#include "rx_debug.h"
#include "rx_misc.h"


RX_SPACE_BEG





typedef struct __rx_edge_tag
{
		rx_state_t		*start;
		rx_state_t		*end;
		rx_edge_t		*next;
}rx_edge_t;

#define __edge_node_size(dsize) (sizeof(rx_edge_t) + dsize)
#define __edge_data(enode) ((void*)((rx_byte*)enode + sizeof(rx_edge_t)))



typedef struct __rx_state_tag
{
		rx_vector_t		*in;
		rx_vector_t		*out;
		
		rx_state_t		*next;
}rx_state_t;

#define __state_node_size(dsize) (sizeof(rx_state_t) + dsize)
#define __state_data(snode) ((void*)((rx_byte*)snode + sizeof(rx_state_t)))


#define __state_is_valid(s) (s->in != NULL && s->out != NULL)


typedef struct __rx_automaton_tag
{
		rx_edge_t				*edge_free;
		rx_state_t				*state_free;
		
		rx_info_t				edge_info;
		rx_info_t				state_info;
		
		rx_alloc_t				alloc;

}rx_automaton_t;

#define __MIN_ALLOC_STATE_SIZE	 16
#define __MIN_ALLOC_EDGE_SIZE	 32


static rx_bool __automaton_is_valid(const rx_automaton_t *atm)
{
		if(atm == NULL)return rx_false;
		if(atm->edge_info.init_f == NULL || atm->edge_info.uninit_f == NULL || atm->edge_info.copy_f == NULL || atm->edge_info.elem_size == 0) return rx_false;
		if(atm->state_info.init_f == NULL || atm->state_info.uninit_f == NULL || atm->state_info.copy_f == NULL || atm->state_info.elem_size == 0)return rx_false;
		
		return rx_true;
}



static rx_state_t* __alloc_state(const void *sour, rx_automaton_t *atm)
{
		rx_state_t* res; size_t i;
		const size_t __alloc_size = __state_node_size(atm->state_info.elem_size);
		
		RX_ASSERT(__automaton_is_valid(atm));
RE_GET:
		if(atm->state_free != NULL)
		{
				res = atm->state_free;
				atm->state_free = res->next;
				res->next = NULL;
		}else
		{
				rx_info_t info;
				rx_init_info(&info);
				info.elem_size = sizeof(void*); 
				rx_install_info(&info);
				
				
				for(i = 0; i < __MIN_ALLOC_STATE_SIZE; ++i)
				{
						rx_state_t *tmp = (rx_state_t*)atm->alloc.alloc_f(__alloc_size, atm->alloc.ctx);
						rx_memset(tmp, __alloc_size, 0);
						tmp->in = rx_vector_create(&info, NULL); 
						tmp->out = rx_vector_create(&info, NULL);
						tmp->next = atm->state_free; 
						atm->state_free = tmp;
				}
				
				goto RE_GET;
		}

		atm->state_info.init_f(__state_data(res), atm->state_info.elem_size);
		atm->state_info.copy_f(__state_data(res), sour, atm->state_info.elem_size);
		return res;
}

static void __free_state(rx_state_t *state, rx_automaton_t *atm)
{
		RX_ASSERT(__automaton_is_valid(atm) && state != NULL);

		rx_vector_clear(state->in); 
		rx_vector_clear(state->out);
		atm->state_info.uninit_f(__state_data(state), atm->state_info.elem_size);
		state->next = atm->state_free;
		atm->state_free = state;
}




static rx_edge_t* __alloc_edge(const void *sour, rx_automaton_t *atm)
{
		rx_edge_t *res; size_t i; 
		const size_t __alloc_size = __edge_node_size(atm->edge_info.elem_size);
		RX_ASSERT(__automaton_is_valid(atm));
RE_GET:
		if(atm->edge_free != NULL)
		{
				res = atm->edge_free;
				atm->edge_free = atm->edge_free->next;
				res->next = NULL;
		}else
		{
				for(i = 0; i < __MIN_ALLOC_EDGE_SIZE; ++i)
				{
						rx_edge_t *tmp = (rx_edge_t*)atm->alloc.alloc_f(__alloc_size, atm->alloc.ctx);
						rx_memset(tmp, 0, __alloc_size);
						tmp->next = atm->edge_free;
						atm->edge_free = tmp;
				}

				goto RE_GET;

		}

		atm->edge_info.init_f(__edge_data(res), atm->edge_info.elem_size);
		atm->edge_info.copy_f(__edge_data(res), sour, atm->edge_info.elem_size);
		return res;
}

static void __free_edge(rx_edge_t *edge, rx_automaton_t *atm)
{
		RX_ASSERT(__automaton_is_valid(atm) && edge != NULL);

		edge->next = atm->edge_free;
		atm->edge_free = edge;
		atm->edge_info.uninit_f(__edge_data(edge), atm->edge_info.elem_size);
		edge->end = edge->start = NULL;

}







rx_state_t* rx_automaton_alloc(rx_automaton_t *atm, const void *state_data)
{
		return __alloc_state(state_data, atm);
}



rx_edge_t* rx_automaton_connect(rx_automaton_t *atm, rx_state_t *start, rx_state_t *end, const void *edge_data)
{
		rx_edge_t* e;
		RX_ASSERT(__state_is_valid(start));
		RX_ASSERT(__state_is_valid(end));
		RX_ASSERT(__automaton_is_valid(atm));
		e = __alloc_edge(edge_data, atm);
		e->start = start;
		e->end = end;

		rx_vector_push_back(start->out, (const void*)&e);
		rx_vector_push_back(end->in, (const void*)&e);
		
		return e;
}

rx_edge_t* rx_automaton_connect_pos(rx_automaton_t *atm, rx_state_t *start, size_t pos, rx_state_t *end, const void *edge_data)
{
		rx_edge_t* e;
		RX_ASSERT(__state_is_valid(start));
		RX_ASSERT(__state_is_valid(end));
		RX_ASSERT(__automaton_is_valid(atm));
		
		e = __alloc_edge(edge_data, atm);
		e->start = start;
		e->end = end;
		
		if(pos < rx_vector_size(start->out))
		{
				rx_vector_insert_pos(start->out, pos, (const void*)&e);

		}else if(pos == rx_vector_size(start->out))
		{
				rx_vector_push_back(start->out, (const void*)&e);
				
		}else
		{
				RX_ASSERT(0);
		}
				
		
		rx_vector_push_back(end->in, (const void*)&e);
		return e;
}

void	rx_automaton_state_edge_swap_order(rx_state_t *state, rx_bool is_out, size_t l, size_t r)
{
		
		rx_vector_t *v;
		size_t count;
		rx_edge_t **tmp_l, **tmp_r;
		rx_edge_t *tmp;

		RX_ASSERT(__state_is_valid(state));
		v = is_out ? state->out : state->in;
		count = rx_vector_size(v);
		RX_ASSERT(l < count && r < count);
		
		if(l == r)return;

		tmp_l = (rx_edge_t**)rx_vector_at(v, l);
		tmp_r = (rx_edge_t**)rx_vector_at(v, r);
		
		tmp = *tmp_l; *tmp_l = *tmp_r; *tmp_r = tmp;
}

void	rx_automaton_state_edge_move_to(rx_state_t *state, rx_bool is_out, size_t l, size_t r)
{
		

		
		rx_vector_t *v;
		size_t count;
		void *ptr = NULL;
		
		rx_edge_t *tmp;

		RX_ASSERT(__state_is_valid(state));
		v = is_out ? state->out : state->in;
		count = rx_vector_size(v);
		RX_ASSERT(l < count && r < count);
		
		if(l == r)return;

		ptr = rx_vector_at(v, l);
		tmp = *(rx_edge_t**)ptr;
		rx_vector_erase(v, ptr);
		rx_vector_insert_pos(v, r, (const void*)&tmp);
}


void	rx_automaton_state_edge_put_back(rx_state_t *state, rx_bool is_out, size_t idx)
{
		rx_vector_t *v;
		size_t count;
		rx_edge_t *tmp;
		void *ptr;

		RX_ASSERT(__state_is_valid(state));
		v = is_out ? state->out : state->in;
		count = rx_vector_size(v);
		RX_ASSERT(idx < count);

		if(idx == count - 1)return;
		
		ptr = rx_vector_at(v, idx);
		tmp = *(rx_edge_t**)ptr;

		rx_vector_erase(v, ptr);
		rx_vector_push_back(v, (const void*)&tmp);


}

void	rx_automaton_state_edge_put_front(rx_state_t *state, rx_bool is_out, size_t idx)
{
		rx_vector_t *v;
		size_t count;
		rx_edge_t *tmp;
		void *ptr;

		RX_ASSERT(__state_is_valid(state));
		v = is_out ? state->out : state->in;
		count = rx_vector_size(v);
		RX_ASSERT(idx < count);

		if(idx == 0)return;
		
		ptr = rx_vector_at(v, idx);
		tmp = *(rx_edge_t**)ptr;

		rx_vector_erase(v, ptr);
		rx_vector_push_front(v, (const void*)&tmp);

}

void rx_automaton_disconnect_edge(rx_automaton_t *atm, rx_state_t *start, rx_edge_t *edge)
{
		rx_int_n i = 0;
		RX_ASSERT(__state_is_valid(start));
		RX_ASSERT(__automaton_is_valid(atm));

		
		i = rx_vector_indexof(start->out, (const void*)&edge);
		RX_ASSERT(i != -1);
		rx_vector_erase_pos(start->out, i);
		i = rx_vector_indexof(edge->end->in, (const void*)&edge);
		RX_ASSERT(i != -1);
		rx_vector_erase_pos(edge->end->in, i);
		__free_edge(edge, atm);

}





void rx_automaton_disconnect(rx_automaton_t *atm, rx_state_t *state)
{
		
		RX_ASSERT(__state_is_valid(state));
		RX_ASSERT(__automaton_is_valid(atm));
		
		while(!rx_vector_is_empty(state->in))
		{
				rx_edge_t *e = *(rx_edge_t**)rx_vector_begin(state->in);
				rx_automaton_disconnect_edge(atm, e->start, e);
		}

		while(!rx_vector_is_empty(state->out))
		{
				rx_edge_t *e = *(rx_edge_t**)rx_vector_begin(state->out);
				rx_automaton_disconnect_edge(atm, state, e);
		}

		__free_state(state, atm);
}


rx_state_t*	rx_automaton_edge_from(rx_edge_t *edge)
{
		RX_ASSERT(edge != NULL);
		return edge->start;
}

rx_state_t*	rx_automaton_edge_to(rx_edge_t *edge)
{
		RX_ASSERT(edge != NULL);
		return edge->end;
}

void*			rx_automaton_edge_data(rx_edge_t *edge)
{
		return edge == NULL ? NULL : __edge_data(edge);
}

void*			rx_automaton_state_data(rx_state_t *state)
{
		return state == NULL ? NULL : __state_data(state);
}

size_t			rx_automaton_state_edge_count(rx_state_t *state, rx_bool is_out)
{
		rx_vector_t *v;
		RX_ASSERT(__state_is_valid(state));
		v = is_out ? state->out : state->in;
		return rx_vector_size(v);
}


rx_edge_t*		rx_automaton_state_edge(rx_state_t *state, size_t idx, rx_bool is_out)
{
		rx_vector_t *v;
		RX_ASSERT(__state_is_valid(state));
		v = is_out ? state->out : state->in;
		RX_ASSERT(idx < rx_vector_size(v));
		return *(rx_edge_t**)rx_vector_at(v, idx);
}

rx_int_n		rx_automaton_state_edge_indexof(rx_state_t *state, rx_bool is_out, const rx_edge_t *edge)
{
		rx_vector_t *v;
		RX_ASSERT(__state_is_valid(state));
		v = is_out ? state->out : state->in;
		return rx_vector_indexof(v, (const void*)&edge);
}




rx_automaton_t* rx_automaton_create(const rx_info_t *state_info, const rx_info_t *edge_info, const rx_alloc_t *palloc)
{
		rx_automaton_t *res;
		RX_ASSERT(state_info != NULL && edge_info != NULL);
		if(palloc == NULL)palloc = rx_mem_default_alloctor();

		res = (rx_automaton_t*)palloc->alloc_f(sizeof(rx_automaton_t), palloc->ctx);
		rx_memset(res, 0, sizeof(rx_automaton_t));

		res->alloc = *palloc;
		res->edge_info = *edge_info;
		rx_install_info(&res->edge_info);
		res->state_info = *state_info;
		rx_install_info(&res->state_info);
		return res;
}

static void __clear_edge_free(rx_automaton_t *atm)
{
		rx_edge_t *e;
		RX_ASSERT(__automaton_is_valid(atm));

		e = atm->edge_free;

		while(e != NULL)
		{
				rx_edge_t *tmp = e->next;
				atm->alloc.dealloc_f(e, atm->alloc.ctx);
				e = tmp;
		}
		atm->edge_free = NULL;
		
}

static void __clear_state_free(rx_automaton_t *atm)
{
		rx_state_t *s;
		RX_ASSERT(__automaton_is_valid(atm));

		s = atm->state_free;
		while(s != NULL)
		{
				rx_state_t *tmp = s->next;
				rx_vector_destroy(s->in);
				rx_vector_destroy(s->out);
				atm->alloc.dealloc_f(s, atm->alloc.ctx);
				s = tmp;
		}

		atm->state_free = NULL;
}


void rx_automaton_trim_mem(rx_automaton_t *atm)
{
		__clear_state_free(atm);
		__clear_edge_free(atm);
}

void rx_automaton_destroy(rx_automaton_t *atm)
{
		if(atm != NULL)
		{
				RX_ASSERT(__automaton_is_valid(atm));
				__clear_state_free(atm);
				__clear_edge_free(atm);
				atm->alloc.dealloc_f(atm, atm->alloc.ctx);
		}



}








static rx_bool __dfs(rx_automaton_t *atm, rx_state_t *root, rx_vector_t *vec, rx_bool (*edge_test_f)(const rx_edge_t*), rx_bool allow_cyclic)
{
		size_t i;  

		RX_ASSERT(__automaton_is_valid(atm) && __state_is_valid(root));
		RX_ASSERT(vec != NULL);
		RX_ASSERT(edge_test_f != NULL);
		
		if(rx_vector_indexof(vec, (const void*)&root) == -1)
		{
				rx_vector_push_back(vec, (const void*)&root);
		}else
		{
				if(!allow_cyclic)
				{
						return rx_false;
				}else
				{
						return rx_true;
				}
		}

		
		

		for(i = 0; i < rx_automaton_state_edge_count(root, rx_true); ++i)
		{
				rx_bool ok;
				rx_edge_t *tmp = rx_automaton_state_edge(root, i, rx_true);
				ok = rx_true;

				if(edge_test_f(tmp))
				{
						ok = __dfs(atm, tmp->end, vec, edge_test_f, allow_cyclic);
				}
				
				if(!ok && !allow_cyclic)return rx_false;
				
		}
		return rx_true;
}



RX_INLINE static rx_bool __bfs(rx_automaton_t *atm, rx_state_t *root, rx_vector_t *vec, rx_bool (*edge_test_f)(const rx_edge_t*), rx_bool allow_cyclic)
{
		size_t i,j; rx_state_t *state, *tmp;

		RX_ASSERT(__automaton_is_valid(atm) && __state_is_valid(root));
		RX_ASSERT(vec != NULL);
		RX_ASSERT(edge_test_f != NULL);
		
		rx_vector_push_back(vec, (const void*)&root);

		for(i = 0; i < rx_vector_size(vec); ++i)
		{
				state = *(rx_state_t**)rx_vector_at(vec, i);
				for(j = 0; j < rx_automaton_state_edge_count(state, rx_true); ++j)
				{
						rx_edge_t *e = rx_automaton_state_edge(state, j, rx_true);
						RX_ASSERT(e->start == state && e->end != NULL);
						if(!edge_test_f(e))
						{
								continue;
						}else
						{
								tmp = e->end;
						
								if(rx_vector_indexof(vec,(const void*)&tmp) == -1)
								{
										rx_vector_push_back(vec, (const void*)&tmp);
								}else
								{
										if(!allow_cyclic)return rx_false;
								}
						}
				}
		}

		return rx_true;

}

RX_INLINE static rx_bool __def_custom_test_func(const rx_edge_t *edge)
{
		edge = edge;
		return rx_true;
}




#define __search_algo __bfs

rx_vector_t* rx_automaton_path(rx_automaton_t *atm, rx_state_t *root, rx_bool (*edge_test_f)(const rx_edge_t*))
{
		rx_vector_t *vec; rx_info_t info;
		RX_ASSERT(__automaton_is_valid(atm));
		RX_ASSERT(__state_is_valid(root));
		
		if(edge_test_f == NULL)edge_test_f = __def_custom_test_func;
		rx_init_info(&info);
		info.elem_size = sizeof(rx_state_t*);

		rx_install_info(&info);
		vec = rx_vector_create(&info, &atm->alloc);

		__search_algo(atm, root, vec, edge_test_f, rx_true);
		return vec;
}



rx_vector_t* rx_automaton_acyclic_path(rx_automaton_t *atm, rx_state_t *root, rx_bool (*edge_test_f)(const rx_edge_t*))
{
		rx_vector_t *vec; rx_info_t info;
		RX_ASSERT(__automaton_is_valid(atm));
		RX_ASSERT(__state_is_valid(root));
		
		if(edge_test_f == NULL)edge_test_f = __def_custom_test_func;
		
		rx_init_info(&info);
		info.elem_size = sizeof(rx_state_t*);
		rx_install_info(&info);
		vec = rx_vector_create(&info, &atm->alloc);

		if(__search_algo(atm, root, vec, edge_test_f, rx_false)) return vec;
		
		rx_vector_destroy(vec);
		return NULL;
}

#undef __search_algo


rx_atm_copy_result_t rx_automaton_copy_state(rx_automaton_t *atm, rx_state_t *root, rx_bool (*edge_test_f)(const rx_edge_t*))
{
		size_t i,j; rx_atm_copy_result_t res;
		rx_vector_t *sour_path, *dest_path;
		rx_info_t info; 

		rx_init_info(&info);
		info.elem_size = sizeof(rx_state_t*);
		rx_install_info(&info);
		
		sour_path = rx_automaton_path(atm, root, edge_test_f);
		dest_path = rx_vector_create(&info, NULL);

		for(i = 0; i < rx_vector_size(sour_path); ++i)
		{
				rx_state_t *s, *d;
				const void *s_data;
				
				s = *(rx_state_t**)rx_vector_at(sour_path, i);
				s_data = rx_automaton_state_data(s);
				d = rx_automaton_alloc(atm, s_data);
				rx_vector_push_back(dest_path, (const void*)&d);
		}

		RX_ASSERT(rx_vector_size(dest_path) == rx_vector_size(sour_path));

		for(i = 0; i < rx_vector_size(sour_path); ++i)
		{
				rx_state_t *s, *d;
				
				s = *(rx_state_t**)rx_vector_at(sour_path, i);
				d = *(rx_state_t**)rx_vector_at(dest_path, i);

				for(j = 0; j < rx_automaton_state_edge_count(s, rx_true); ++j)
				{
						rx_state_t *tmp;
						rx_int_n idx;
						rx_edge_t *e = rx_automaton_state_edge(s, j, rx_true);

						idx = rx_vector_indexof(sour_path, (const void*)&(e->end));
						RX_ASSERT(idx != -1);

						tmp = *(rx_state_t**)rx_vector_at(dest_path, idx);
						rx_automaton_connect(atm, d, tmp, rx_automaton_edge_data(e));
				}
		}


		res.sour = sour_path;
		res.dest = dest_path;
		return res;


}






RX_SPACE_END

